제5장 정렬 알고리즘

제5장 정렬 알고리즘
1. 5.8 기수 정렬(Radix Sort)
2. 문서에 대하여

5.8 기수 정렬(Radix Sort)

컴퓨터 자료가 디지털 임을 착안하여 생긴 정렬방법. (2진수를 이용)

5.8.1 기수 교환 정렬(Radix Exchange Sort)의 전략

왼쪽 비트에서 오른쪽 비트로 검사.
재귀호출에 의한 정렬.
약간의 스택(재귀호출을 위한)을 위한 메모리 필요.(소량)
기수교환 정렬 알고리즘 (a, N, b)
1. 만약 n > 1 이고 b <= 0 이면
1.1 N크기의 a배열을 분할하여 비트 1이 시작되는 곳(분할 지점)을 j에 할당
1.2 기수 교환 정렬 알고리즘(a, j, b-1)
1.3 기수 교환 정렬 알고리즘(a+j, N-j, b-1)

5.8.2 기수 교환 정렬의 실제

p376 참고.

알파벳	2진수
O	01001111
R	01010010
A	01000001
C	01000011
L	01001100
E	01000101
C	01000011
L	01001100
U	01010101
B	01000010

5.8.3 C로 구현한 기수 교환 정렬

자바


package com.oracleclub.study.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class RadixSort {
	
	private static final boolean DEBUG = false;
	
	
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	
	/**
	 * 10진수->2진수
	 * @param decimal
	 * @param size
	 * @return
	 */
	public static String toString(int decimal, int size) {
		Stack<Byte> stack = new Stack<Byte>();
		
		while(decimal > 1) {
			byte binary = (byte) (decimal % 2);			
			stack.push(binary);			
			decimal /= 2;
		}
		stack.push((byte)decimal);
		

		StringBuffer sb = new StringBuffer();
		// 앞에 0 채우기.
		if(stack.size() < size) {
			int loop = size - stack.size();
			for(int i=0; i<loop; i++) {
				sb.append("0");
			}
		}
		
		// stack 처리.
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
	
		return sb.toString();
		
	}
	
	/**
	 * 2진수->10진수
	 * @param binary
	 * @return
	 */
	public static int toDecimal(String binary) {
		
		int decimal = 0;                  // 10진수 값이 저장 될 변수 초기화
        int i = binary.length()-1;    // String 인덱스 카운터 (n-1 to 0)
        int j = 0;                            // 2진수 인덱스 카운터 (0 to n-1)
                                                // n = String 길이

        while (i >= 0) {
           // String 인덱스 값이 1일 경우 2의 j 배수만큼 decimal 변수에 합산
           if (binary.charAt(i) == '1')
               decimal += Math.pow(2, j);

           i--;          // String 인덱스 감소
           j++;          // 2진수 인덱스 증가
       }

       return decimal;         // 변환된 10진수 결과 값 리턴
	}
	
	/**
	 * 문자->2진수.
	 * @param c
	 * @return
	 */
	public static String toString(char c) {
		byte b = (byte) c;
		return toString(b, 8);
	}
	
	void radix_exchange_sort(List<Short> a, int begin_index, int n, short b) {

		if(DEBUG)
			System.out.println("radix_exchange_sort(List<Short>, " + begin_index 
								+ " , " + n + ", " + b + ")");
			
		short t;
		int i;
		int j;
		
		if(n>1 && b>=0) {
			i = begin_index;
			j = n -1;
			
			while(true) {
				while(bits(a.get(i), b, (short)1) == 0 && i < j) {
					i++;
				}
				if(DEBUG)
					System.out.println("left->" + i);
				
				while(bits(a.get(j), b, (short)1) != 0 && i < j) {
					j--;			
				}
				if(DEBUG)
					System.out.println("right->" + j);
				
				if(i>=j){
					break;
				}
				
				t = a.get(i);
				a.set(i, a.get(j));
				a.set(j, t);
				
				printList(a);
				
				
				
			}				
							
			if(bits(a.get(n-1), b, (short)1) == 0) {
				j++;
			}
			
			int bb = b-1;
			
			radix_exchange_sort(a, begin_index, j,  (short)bb);			
			radix_exchange_sort(a, begin_index + j, n-j, (short)bb);			
		}
	}

	public static void printList(List<Short> lst) {
		System.out.print("[[[");
		for(short s: lst) {
						
			byte aaa = (byte) (s & 0xff);
			
			System.out.print((char)aaa);
			
		}
		System.out.println("]]]");
		
	}
	
	
	public static void main(String[] args) {
		RadixSort sort = new RadixSort();
		
		List<Short> lst = new ArrayList<Short>();
		
		lst.add((short)RadixSort.toDecimal("01000001")); // A
		lst.add((short)RadixSort.toDecimal("01001100")); // L
		lst.add((short)RadixSort.toDecimal("01000111")); // G
		lst.add((short)RadixSort.toDecimal("01001111")); // O
		lst.add((short)RadixSort.toDecimal("01010010")); // R
		lst.add((short)RadixSort.toDecimal("01001001")); // I
		lst.add((short)RadixSort.toDecimal("01010100")); // T
		lst.add((short)RadixSort.toDecimal("01001000")); // H
		lst.add((short)RadixSort.toDecimal("01001101")); // M
		
		
		System.out.println(Collections.checkedList(lst, Short.class));
	}


}

5.8.4 기수 교환 정렬의 분석

숫자의 대소를 따지지 않고, 비트를 따지기 때문에 입력 자료에 별 상관없이 뛰어난 성능 (p379)
비트를 사용하기 때문에 비트가 많이 들어가는 자료형에서는 성능이 좋지 못하다.
부동소숫점연산을 사용하는 데이터는 비트연산을 할 수 없다.
32비트 시스템에서의 자료형.

자바 자료형	비트
Byte	8
Short	16
Integer	32
Long	64
String	무한대

5.8.5 기수 교환 정렬의 개선(비재귀판)

자바


package com.oracleclub.study.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class RadixExSort {
	
	static final boolean DEBUG = false;
	
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	
	void radix_exchange_sort1(List<Integer> list) {
		int n = list.size();
		int t, i, j;
		int l, r;
		int b;
		Stack<Integer> stack = new Stack<Integer>();
		
		b = 31;
		l = 0;
		r = n-1;
		
		stack.push(b);
		stack.push(r);
		stack.push(l);
		
		while(!stack.isEmpty()) {
			l = stack.pop();
			r = stack.pop();
			b = stack.pop();
			
			if(r>1 && b>=0) {
				i = l;
				j = r;
				while(true) {
					while(bits(list.get(i), b, 1) == 0 && i < j) {
						i++;
					}
					while(bits(list.get(j), b, 1) != 0 && i < j) {
						j--;						
					}
					
					if(i>=j) {
						break;
					}
					
					t = list.get(i);
					list.set(i, list.get(j));
					list.set(j, t);
				}
				
				if(bits(list.get(r), b, 1) == 0) {
					j++;
				}
				
				stack.push(b-1);
				stack.push(r);
				stack.push(j);
				stack.push(b-1);
				stack.push(j-1);
				stack.push(l);
			}
		}
				
		
	}
	
	public static void main(String[] args) {
		RadixExSort s = new RadixExSort();
		
		List<Integer> list = new ArrayList<Integer>();
		list.add(10);
		list.add(9);
		list.add(11);
		list.add(122);
		list.add(14);
		list.add(1);
		
		System.out.println("before=" + Collections.checkedCollection(list, Integer.class));
		s.radix_exchange_sort1(list);
		System.out.println("after=" + Collections.checkedCollection(list, Integer.class));
	}
	
}

5.8.6 직접 기수 정렬(Straight Radix Sort)의 전략

오른쪽 비트에서 왼쪽 비트로 검사.
분포수세기에 의한 비 재귀적 방법으로 정렬.
- 키가 많이 중복되는 경우에 가장 효율적.
- 기수정렬은 비트연산(0 또는 1)만 사용하기 때문에, 키가 많이 중복된다.
분포를 저장하기 위한 배열과 똑같은 크기의 배열이 필요

하지만 속도는 정렬중에서 가장 빠름. => 메모리를 많이 사용할수록 속도가 빨라짐.

5.8.7 직접 기수 정렬의 실제

p382 참고.

알파벳	2진수
O	01001111
R	01010010
A	01000001
C	01000011
L	01001100
E	01000101
C	01000011
L	01001100
U	01010101
B	01000010

5.8.8 C로 구현한 직접 기수 정렬

자바


package com.oracleclub.study.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 직접 기수 정렬.
 * @author 장선웅
 *
 */
public class RadixSort2 {

	static final boolean DEBUG = false;
	
	static final int W = 16;
	static final int M = 4;
	static final int MV = 1 << M;
	
	int bits(int x, int k, int j) {
		if(DEBUG)
			System.out.println("x=" + x + ", k=" + k + ", j=" + j);
		return (x >> k) & ~(~0 << j);
	}
	
	public void straight_radix_sort(List<Integer> list) {
		
		int n = list.size();
		int i, j;
		int b[] = new int[n]; 
		int count[] = new int[MV];
		
		for(i=0; i<W/M; i++) {
			for(j=0; j<MV; j++) {
				count[j] = 0;
			}
			
			for(j=0; j<n; j++) {
				count[bits(list.get(j), i*M, M)]++;
			}
			for(j=1; j<MV; j++) {
				count[j] = count[j] + count[j-1];
			}
			
			for(j=n-1; j>=0; j--) {
				b[--count[bits(list.get(j), i*M, M)]] = list.get(j);
			}
			for(j=0; j<n; j++) {
				list.set(j, b[j]);
			}			
		}
		
		b = null;
		count = null;
	}
	
	public static void main(String[] args) {
		RadixSort2 s = new RadixSort2();
		
		List<Integer> list = new ArrayList<Integer>();
		list.add(10);
		list.add(9);
		list.add(11);
		list.add(122);
		list.add(14);
		list.add(1);
		
		System.out.println("before=" + Collections.checkedCollection(list, Integer.class));
		s.straight_radix_sort(list);
		System.out.println("after=" + Collections.checkedCollection(list, Integer.class));
	}
}

결과


before=[10, 9, 11, 122, 14, 1]
after=[1, 9, 10, 11, 14, 122]

5.8.9 직접 기수 정렬의 분석

장점 :
1. 직접기수정렬은 입력자료에 무관하다.
2. if문이 없는 분포수세기를 활용하였기 ?문에 아주 빠른 속도를 나타낸다.
단점 :
3. 메모리를 너무 많이 사용한다.
4. 정렬키의 비트수가 일정하고, 적어야 한다.

5.8.10 두 가지 기수 정렬법의 일반화

제한된 정렬키를 가지고 있기때문에 일반화하기 어렵다.
결국 각 상황에 맞게 사용해야한다.

문서에 대하여

이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
최초작성자 : VLDB
최초작성일 : 2009년 4월 8일
이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

5.8 기수 정렬(Radix Sort) (by sily20) [2009.05.04]

제5장 정렬 알고리즘

5.8 기수 정렬(Radix Sort)

5.8.1 기수 교환 정렬(Radix Exchange Sort)의 전략

5.8.2 기수 교환 정렬의 실제

5.8.3 C로 구현한 기수 교환 정렬

5.8.4 기수 교환 정렬의 분석

5.8.5 기수 교환 정렬의 개선(비재귀판)

5.8.6 직접 기수 정렬(Straight Radix Sort)의 전략

5.8.7 직접 기수 정렬의 실제

5.8.8 C로 구현한 직접 기수 정렬

5.8.9 직접 기수 정렬의 분석

5.8.10 두 가지 기수 정렬법의 일반화

문서에 대하여